Exhibiting nondeterminism.

<algorithm> A property of a computation which may have more than one result. One way to implement a nondeterministic algorithm is using backtracking, another is to explore (all) possible solutions in parallel. (1995-04-13)

A nondeterministic programming language is a language which can specify, at certain points in the program (called "choice points"), various alternatives for program flow. Unlike an if-then statement, the method of choice between these alternatives is not directly specified by the programmer; the program must decide at run time between the alternatives, via some general method applied to all choice points.

In the theory of computation, a generalized nondeterministic finite automaton (GNFA), also known as an expression automaton or a generalized nondeterministic finite state machine, is a variation of a

In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine.

<complexity> A normal (deterministic) Turing Machine that has a "guessing head" - a write-only head that writes a guess at a solution on the tape first, based on some arbitrary internal algorithm. The regular Turing Machine then runs and returns "yes" or "no" to indicate whether the solution is correct. A nondeterministic Turing Machine can solve nondeterministic polynomial time computational {decision problems} in a number of steps that is a polynomial function of the size of the input (1995-04-27)

<complexity> (NP) A set or property of computational {decision problems} solvable by a nondeterministic Turing Machine in a number of steps that is a polynomial function of the size of the input. The word "nondeterministic" suggests a method of generating potential solutions using some form of nondeterminism or "trial and error". This may take exponential time as long as a potential solution can be verified in polynomial time. NP is obviously a superset of P (polynomial time problems solvable by a deterministic Turing Machine in {polynomial time}) since a deterministic algorithm can be considered as a degenerate form of nondeterministic algorithm. The question then arises: is NP equal to P? I.e. can every problem in NP actually be solved in polynomial time? Everyone's first guess is "no", but no one has managed to prove this; and some very clever people think the answer is "yes". If a problem A is in NP and a polynomial time algorithm for A could also be used to solve problem B in polynomial time, then B is also in NP. See also Co-NP, NP-complete. [Examples?] (1995-04-10)

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE.

In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time O(f(n)). Here O is the big O notation, f is some function, and n is the size of the input (for which the problem is to be decided).

<complexity> (NPC, Nondeterministic Polynomial time complete) A set or property of computational decision problems which is a subset of NP (i.e. can be solved by a nondeterministic Turing Machine in polynomial time), with the additional property that it is also NP-hard. Thus a solution for one NP-complete problem would solve all problems in NP. Many (but not all) naturally arising problems in class NP are in fact NP-complete. There is always a polynomial-time algorithm for transforming an instance of any NP-complete problem into an instance of any other NP-complete problem. So if you could solve one you could solve any other by transforming it to the solved one. The first problem ever shown to be NP-complete was the satisfiability problem. Another example is {Hamilton's problem}. See also computational complexity, halting problem, Co-NP, NP-hard. http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/. [Other examples?] (1995-04-10)